package mid

func NumberOfRightTriangles(grid [][]int) int64 {
	m, n := len(grid), len(grid[0])
	col := make([]int, n)
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			col[i] += grid[j][i]
		}
	}
	var res int64
	for i := 0; i < m; i++ {
		row := 0
		for j := 0; j < n; j++ {
			row += grid[i][j]
		}
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				res += int64(row-1) * int64(col[j]-1)
			}
		}
	}
	return res
}
